/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/palindromic-ranges
   @Language: C++
   @Datetime: 19-04-25 17:01
   */

class Solution {
	bool ispalindrome(int num){
		string str=to_string(num);
		for(int i=0, j=str.length()-1; i<j;)
			if(str[i++]!=str[j--]) return false;
		return true;
	}
public:
	/**
	 * @param L: A positive integer
	 * @param R: A positive integer
	 * @return:  the number of interesting subranges of [L,R]
	 */
	int PalindromicRanges(int L, int R) {
		vector<int> dp(R-L+2,0);
		int count=0;
		for(int i=L; i<=R; ++i){
			if(ispalindrome(i)) dp[i-L+1]++;
			dp[i-L+1]+=dp[i-L];
		}
		for(int i=L; i<=R; ++i){
			for(int j=i; j<=R; ++j){
				if((dp[j-L+1]-dp[i-L])&1) continue;
				count++;
			}
		}
		return count;
	}
};
